package com.wlc.base.sorting.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 王立朝
 * @date 2022/2/21
 * @description: 排序demo
 */
public class SortDemo {

    public static int[] initArray(int length) {
        int[] array = new int[length];
        for (int i = 0; i < length; i++) {
            array[i] = new Random().nextInt(100);
        }
        return array;
    }

    /**
     * 第二名
     * @param nums
     * @return
     */
    public static int[] binaryInsertionSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int insertNum = nums[i];
            int insertIndex = -1;
            int start = 0;
            int end = i - 1;
            while (start <= end) {
                int mid = start + (end - start) / 2;
                if (insertNum > nums[mid]) {

                    start = mid + 1;
                } else if (insertNum < nums[mid]) {

                    end = mid - 1;
                } else {
                    insertIndex = mid + 1;
                    break;
                }
            }
            if (insertIndex == -1) {

                insertIndex = start;
            }
            if (i - insertIndex >= 0) {

                System.arraycopy(nums, insertIndex, nums, insertIndex + 1, i - insertIndex);
            }
            nums[insertIndex] = insertNum;


        }
        return nums;
    }

    /**
     * 插入排序
     * 很快，第一名
     * @param nums
     * @return
     */
    public static int[] insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int insertNum = nums[i];
            int insertIndex;
            for (insertIndex = i - 1; insertIndex >= 0 && nums[insertIndex] > insertNum; insertIndex--) {
                nums[insertIndex + 1] = nums[insertIndex];
            }
            nums[insertIndex + 1] = insertNum;
        }
        return nums;
    }


    public static long comapare1(int[] array) {
        long start = System.currentTimeMillis();
        int[] array2 = binaryInsertionSort(array);
        long end = System.currentTimeMillis();
        long time = end - start;
        Arrays.stream(array2).forEach(System.out::println);
        System.out.println("============================================");
        return time;
    }

    public static long comapare2(int[] array) {
        long start = System.currentTimeMillis();
        int[] array2 = insertionSort(array);
        System.out.println("================排序后");
        Arrays.stream(array2).forEach(e->{
            System.out.println(e);
        });
        long end = System.currentTimeMillis();
        long time = end - start;
        //Arrays.stream(array2).forEach(System.out::println);
        System.out.println("============================================");
        return time;
    }

    public static void main(String[] args) {
        int[] array = initArray(10);
        //long time1 = comapare1(array);
        long time2 = comapare2(array);


        //System.out.println("time1 = " + time1);
        System.out.println("time2 = " + time2);


    }
}
